package main

import "fmt"

/*
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。
*/

func coinChange(coins []int, amount int) int {
	// dp[i] 表示凑成金额 i 所需的最少硬币数
	dp := make([]int, amount+1)

	// 初始化：除了 dp[0] = 0，其他都设为一个较大的值
	for i := 1; i <= amount; i++ {
		dp[i] = amount + 1 // 设置为不可能的值
	}

	// 动态规划
	for i := 1; i <= amount; i++ { // 金额 从 1~amount
		for _, coin := range coins { // 遍历每个硬币面额
			if coin <= i {
				dp[i] = min(dp[i], dp[i-coin]+1) // 金额i的最小硬币数 = min(当前i的最小硬币数, i-coin的最小硬币数+1)
			}
		}
	}

	// 如果 dp[amount] 仍然是初始值，说明无法凑成
	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	// 测试用例 1
	coins1 := []int{1, 2, 5}
	amount1 := 11
	result1 := coinChange(coins1, amount1)
	fmt.Printf("coins = %v, amount = %d, result = %d\n", coins1, amount1, result1)

	// 测试用例 2
	coins2 := []int{2}
	amount2 := 3
	result2 := coinChange(coins2, amount2)
	fmt.Printf("coins = %v, amount = %d, result = %d\n", coins2, amount2, result2)

	// 测试用例 3
	coins3 := []int{1}
	amount3 := 0
	result3 := coinChange(coins3, amount3)
	fmt.Printf("coins = %v, amount = %d, result = %d\n", coins3, amount3, result3)
}
